package main

import "sort"

func makeResultItem(accountName string, emails map[string]struct{}) []string {
	var accountEmailArr []string
	for e := range emails {
		accountEmailArr = append(accountEmailArr, e)
	}
	sort.Slice(accountEmailArr, func(i, j int) bool {
		return accountEmailArr[i] < accountEmailArr[j]
	})
	resultItem := []string{accountName}
	resultItem = append(resultItem, accountEmailArr...)
	return resultItem
}

func accountsMerge(accounts [][]string) [][]string {
	emailMap := make(map[string][]int) // email -> index
	for i, strs := range accounts {
		for _, email := range strs[1:] {
			emailMap[email] = append(emailMap[email], i)
		}
	}
	var result [][]string
	for i, account := range accounts {
		if account == nil {
			continue
		}
		accounts[i] = nil
		accountName := account[0]
		emails := make(map[string]struct{})
		queue := account[1:] // emails, 队列中 email 所属的 account 应已被置为 nil
		for len(queue) > 0 {
			email := queue[0]
			queue = queue[1:]
			emails[email] = struct{}{}
			otherAccounts := emailMap[email]
			for _, j := range otherAccounts {
				account := accounts[j]
				if account == nil {
					continue
				}
				for _, email := range account[1:] {
					emails[email] = struct{}{}
					queue = append(queue, email)
				}
				accounts[j] = nil
			}
		}
		result = append(result, makeResultItem(accountName, emails))
	}
	return result
}

func main() {
	accounts := [][]string{
		{"1", "0", "1"}, // 0
		{"1", "3", "4"}, // 1 v
		{"1", "4", "5"}, // 2
		{"1", "2", "3"}, // 3
		{"1", "1", "2"}, // 4
	}
	result := accountsMerge(accounts)
	println(result)
}
